1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <cstdio>
#include <algorithm>
const int maxn = 105;
using namespace std;
int n, m, ex, ey; char str[maxn][maxn];
short f[maxn][maxn][maxn][maxn], p[maxn][maxn], q[maxn][maxn];
short max(short x, int y){
if (x < y) return y;
return x;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
p[i][j] = p[i][j - 1]; q[i][j] = q[i - 1][j];
if (str[i][j] == 'E') ex = i, ey = j;
else if (str[i][j] == 'o') p[i][j]++, q[i][j]++;
}
for (int i = 0; i <= ex - 1; i++)
for (int j = 0; j <= ey - 1; j++)
for (int x = 0; x <= n - ex; x++)
for (int y = 0; y <= m - ey; y++){
int L = max(ex - i, x + 1), R = min(n - i, ex + x);
if (L <= R){
f[i][j + 1][x][y] = max(f[i][j + 1][x][y], f[i][j][x][y] + (ey - j - 1 >= y + 1) * (q[R][ey - j - 1] - q[L - 1][ey - j - 1]));
f[i][j][x][y + 1] = max(f[i][j][x][y + 1], f[i][j][x][y] + (m - j >= ey + y + 1) * (q[R][ey + y + 1] - q[L - 1][ey + y + 1]));
}
L = max(ey - j, y + 1), R = min(m - j, ey + y);
if (L <= R){
f[i + 1][j][x][y] = max(f[i + 1][j][x][y], f[i][j][x][y] + (ex - i - 1 >= x + 1) * (p[ex - i - 1][R] - p[ex - i - 1][L - 1]));
f[i][j][x + 1][y] = max(f[i][j][x + 1][y], f[i][j][x][y] + (n - i >= ex + x + 1) * (p[ex + x + 1][R] - p[ex + x + 1][L - 1]));
}
}
printf("%d\n", f[ex - 1][ey - 1][n - ex][m - ey]);
return 0;
}
|